{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Rabbits in Forest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numRabbits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #森林中的兔子"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>森林中有未知数量的兔子。提问其中若干只兔子<strong> \"还有多少只兔子与你（指被提问的兔子）颜色相同?\"</strong> ，将答案收集到一个整数数组 <code>answers</code> 中，其中 <code>answers[i]</code> 是第 <code>i</code> 只兔子的回答。</p>\n",
    "\n",
    "<p>给你数组 <code>answers</code> ，返回森林中兔子的最少数量。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>answers = [1,1,2]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>\n",
    "两只回答了 \"1\" 的兔子可能有相同的颜色，设为红色。 \n",
    "之后回答了 \"2\" 的兔子不会是红色，否则他们的回答会相互矛盾。\n",
    "设回答了 \"2\" 的兔子为蓝色。 \n",
    "此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。 \n",
    "因此森林中兔子的最少数量是 5 只：3 只回答的和 2 只没有回答的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>answers = [10,10,10]\n",
    "<strong>输出：</strong>11\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= answers.length &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= answers[i] &lt; 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [rabbits-in-forest](https://leetcode.cn/problems/rabbits-in-forest/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [rabbits-in-forest](https://leetcode.cn/problems/rabbits-in-forest/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,2]', '[10,10,10]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        answers.sort()\n",
    "        data=set(answers)\n",
    "        ans=0\n",
    "        for num in data:\n",
    "            if answers.count(num)%(num+1)==0:\n",
    "                a=answers.count(num)//(num+1)-1\n",
    "                ans+=(a+1)*(num+1)\n",
    "            else:\n",
    "                a=answers.count(num)//(num+1)\n",
    "                ans+=(a+1)*(num+1)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        mp=Counter(answers)\n",
    "        res=0\n",
    "        for ans,num in mp.items():\n",
    "            res+=(num+ans)//(ans+1)*(ans+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        count = Counter(answers)\n",
    "        ans = sum((x + y) // (y + 1) * (y + 1) for y, x in count.items())\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        dic = {}\n",
    "        for ans in answers:\n",
    "            dic[ans] = dic.get(ans, 0)+1\n",
    "        res = 0\n",
    "        for item in dic.items():\n",
    "            if item[0] == 0:    res+= item[1]\n",
    "            elif item[1] % (item[0]+1)== 0:\n",
    "                res += item[1]\n",
    "            else:\n",
    "                res += (item[1] // (item[0]+1)+1) * (item[0]+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self,answers:List[int])->int:\n",
    "        count=Counter(answers)\n",
    "        ans=sum((x+y)//(y+1)*(y+1) for y,x in count.items())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        rabbit_num_map = defaultdict(int)\n",
    "        for i in answers:\n",
    "            rabbit_num_map[i + 1] += 1\n",
    "\n",
    "        ans = 0\n",
    "        for k, v in rabbit_num_map.items():\n",
    "            ans += v // k * k + bool(v % k) * k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        import math\n",
    "        hash = {}\n",
    "        res = 0\n",
    "        for i in answers:\n",
    "            if i not in hash:\n",
    "                hash[i] = 1\n",
    "            else:\n",
    "                hash[i] += 1\n",
    "        for j in hash:\n",
    "            hash[j] = max(1, math.ceil(hash[j]/(j+1)))\n",
    "            res += hash[j]*(j+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        cnt = Counter(answers)\n",
    "        ans = 0\n",
    "        for x in cnt:\n",
    "            ans += ceil((cnt[x])/(x+1))*(x+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        ret = 0\n",
    "        for k,v in Counter(answers).items():\n",
    "            ret += (k + v) // (k + 1) * (k + 1)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numRabbits(self, answers: List[int]) -> int:\r\n",
    "        res = 0\r\n",
    "        dic = {}\r\n",
    "        for v in answers:\r\n",
    "            if v in dic:\r\n",
    "                dic[v] += 1\r\n",
    "            else:\r\n",
    "                dic[v] = 1\r\n",
    "        for k in dic:\r\n",
    "            cnt = dic[k]\r\n",
    "            val = 0\r\n",
    "            if cnt % (k + 1):\r\n",
    "                val += 1\r\n",
    "            val += cnt // (k + 1)\r\n",
    "            res += val * (k + 1)\r\n",
    "        return(res)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        res=0\n",
    "        dic={}\n",
    "        for i in answers:\n",
    "            v=i+1\n",
    "            if v not in dic.keys():\n",
    "                dic[v]=-1\n",
    "            dic[v]=(dic[v]+1)%v\n",
    "            if dic[v]==0:\n",
    "                res+=v\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        rabbit_num_map = defaultdict(int)\n",
    "        for i in answers:\n",
    "            rabbit_num_map[i + 1] += 1\n",
    "\n",
    "        ans = 0\n",
    "        for k, v in rabbit_num_map.items():\n",
    "            ans += v // k * k + bool(v % k) * k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        answers.sort()\n",
    "        data=set(answers)\n",
    "        ans=0\n",
    "        for num in data:\n",
    "            if answers.count(num)%(num+1)==0:\n",
    "                a=answers.count(num)//(num+1)-1\n",
    "                ans+=(a+1)*(num+1)\n",
    "            else:\n",
    "                a=answers.count(num)//(num+1)\n",
    "                ans+=(a+1)*(num+1)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numRabbits(self, answers: List[int]) -> int:\r\n",
    "        res = 0\r\n",
    "        dic = {}\r\n",
    "        for v in answers:\r\n",
    "            if v in dic:\r\n",
    "                dic[v] += 1\r\n",
    "            else:\r\n",
    "                dic[v] = 1\r\n",
    "        for k in dic:\r\n",
    "            cnt = dic[k]\r\n",
    "            if cnt % (k + 1):\r\n",
    "                res += k + 1\r\n",
    "            res += cnt // (k + 1) * (k + 1)\r\n",
    "        return(res)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        cnt = Counter(answers)\n",
    "        ans = 0\n",
    "        for k, v in cnt.items():\n",
    "            mx = k + 1\n",
    "            ans += (v + mx - 1) // mx * mx \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        counter = {}\n",
    "        number = 0\n",
    "        \n",
    "        for a in answers:\n",
    "            if a == 0:\n",
    "                number += 1\n",
    "            elif a not in counter or counter[a] == 0:\n",
    "                counter[a] = a\n",
    "                number += (a + 1)\n",
    "            elif counter[a] != 0:\n",
    "                counter[a] -= 1\n",
    "\n",
    "        return number\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        answers.sort()\n",
    "        a = -1\n",
    "        ans = 0\n",
    "        for i in range(len(answers)):\n",
    "            if answers[i] != a:\n",
    "                num = 0\n",
    "                for j in range(i, len(answers)):\n",
    "                    if answers[j] != answers[i]:\n",
    "                        break\n",
    "                    num += 1\n",
    "                n = answers[i]\n",
    "                # print(n)\n",
    "                ans += (ceil(num / (n + 1)) * (n + 1))\n",
    "                a = answers[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        dic = {}\n",
    "        res = 0\n",
    "        for a in answers:\n",
    "            if dic.get(a, 0) == 0:\n",
    "                res += (a + 1)\n",
    "                dic[a] = (dic.get(a, 0) + a)\n",
    "            else:\n",
    "                dic[a] = dic[a] - 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        dic = {}\n",
    "        for i in answers:\n",
    "            if i+1 in dic:\n",
    "                dic[i+1] += 1\n",
    "            else:\n",
    "                dic[i+1] = 1\n",
    "        ans = 0\n",
    "        for i in dic.keys():\n",
    "            if dic[i]%(i) != 0:\n",
    "                ans += (dic[i]//(i)+1)*i\n",
    "            else:\n",
    "                ans += dic[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        count = collections.Counter(answers)\n",
    "\n",
    "        return sum((count[x] + x) // (x + 1) * (x + 1) for x in count)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        l = dict()\n",
    "\n",
    "        count = 0\n",
    "        for i in answers:\n",
    "            if (i + 1) not in l:\n",
    "                l[i+1] = i\n",
    "                count += (i+1)\n",
    "                continue\n",
    "            \n",
    "            if (i + 1) in l:\n",
    "                if l[i+1] != 0:\n",
    "                    l[i+1] -= 1\n",
    "                else:\n",
    "                    l[i+1] = i\n",
    "                    count += (i+1)\n",
    "        \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        count = Counter(answers)\n",
    "        ans = sum((x + y) // (y + 1) * (y + 1) for y, x in count.items())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "\n",
    "        nums = 0\n",
    "        dict = {}\n",
    "\n",
    "        for i in answers :\n",
    "            if i in dict :\n",
    "                dict[i] += 1\n",
    "                if dict[i] == i + 1 :\n",
    "                    nums = nums + i + 1\n",
    "                    del dict[i]\n",
    "            else :\n",
    "                dict[i] = 1\n",
    "                if dict[i] == i + 1 :\n",
    "                    nums = nums + i + 1\n",
    "                    del dict[i]\n",
    "        for i in dict.keys() :\n",
    "            nums = nums + i + 1\n",
    "        \n",
    "        return nums\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        count = Counter(answers)\n",
    "        ans = sum((x + y) // (y + 1) * (y + 1) for y, x in count.items())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        dic = defaultdict(int)\n",
    "        for ans in answers:\n",
    "            dic[ans] += 1\n",
    "        count_num = 0\n",
    "        for key in dic:\n",
    "            if dic[key] <= key + 1:\n",
    "                count_num += key+1\n",
    "                continue\n",
    "            while dic[key] > key+1:\n",
    "                count_num += (key+1)\n",
    "                dic[key] -= (key+1)\n",
    "            if dic[key] > 0:\n",
    "                count_num += key+1\n",
    "        return count_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        answers.sort()\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        n = len(answers)\n",
    "        while i < n:\n",
    "            cur = answers[i]\n",
    "            ans += (cur+1)\n",
    "            while cur > 0 and i + 1 < n and answers[i] == answers[i+1]:\n",
    "                cur -= 1\n",
    "                i += 1\n",
    "            i += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "        # count = Counter(answers)\n",
    "        # ans = sum((x + y) // (y + 1) * (y + 1) for y, x in count.items())\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        count = Counter(answers)\n",
    "        ans = sum((x + y) // (y + 1) * (y + 1) for y, x in count.items())\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        #应该让「同一颜色的兔子数量」尽量多，从而实现「总的兔子数量」最少。\n",
    "        answers.sort()\n",
    "        i, ans, n = 0, 0, len(answers)\n",
    "        while i < n:\n",
    "            cur = answers[i]\n",
    "            ans += (cur + 1)\n",
    "            while cur > 0 and i + 1 < len(answers) and answers[i] == answers[i+1]:\n",
    "                #将后面的 cnt 个 cnt 进行忽略。\n",
    "                cur -= 1\n",
    "                i += 1\n",
    "            i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numRabbits(self, answers: List[int]) -> int:\r\n",
    "        res = 0\r\n",
    "        dic = {}\r\n",
    "        for v in answers:\r\n",
    "            if v in dic:\r\n",
    "                dic[v] += 1\r\n",
    "            else:\r\n",
    "                dic[v] = 1\r\n",
    "        for k in dic:\r\n",
    "            cnt = dic[k]\r\n",
    "            val = 0\r\n",
    "            if cnt % (k + 1):\r\n",
    "                val += 1\r\n",
    "            val += cnt // (k + 1)\r\n",
    "            res += val * (k + 1)\r\n",
    "        return(res)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        dic = {}\n",
    "        for ans in answers:\n",
    "            dic[ans] = dic.get(ans, 0)+1\n",
    "        res = 0\n",
    "        for answer, count in dic.items():\n",
    "            if answer == 0 or count % (answer+1)== 0:\n",
    "                res += count\n",
    "            else:\n",
    "                res += (count // (answer+1)+1) * (answer+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        def lt781(answers):\n",
    "            answers.sort()\n",
    "            pairs=[]\n",
    "            st=0\n",
    "            for i in range(len(answers)):\n",
    "                if answers[i]!=answers[st]:\n",
    "                    pairs.append([answers[st]+1,i-st])\n",
    "                    st=i\n",
    "            pairs.append([answers[st]+1, len(answers) - st])\n",
    "            res=0\n",
    "            for a,b in pairs:\n",
    "                res+=math.ceil(b/a)*a\n",
    "            return res\n",
    "        return lt781(answers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numRabbits(self, answers: List[int]) -> int:\r\n",
    "        ans = 0\r\n",
    "        rec = dict()\r\n",
    "        for i in answers:\r\n",
    "            rec.setdefault(i, 0)\r\n",
    "            rec[i] += 1\r\n",
    "        for i in rec:\r\n",
    "            if i == 0:\r\n",
    "                ans += rec[i]\r\n",
    "            elif i + 1 >= rec[i]:\r\n",
    "                ans += i + 1\r\n",
    "            else:\r\n",
    "                ans += (i + 1) * ceil(rec[i] / (i + 1))\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        count = Counter(answers)\n",
    "        ans = sum((x + y) // (y + 1) * (y + 1) for y, x in count.items())\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        dic = {}\n",
    "        for i in range(len(answers)):\n",
    "            if answers[i] + 1 not in dic:              \n",
    "                dic[answers[i] + 1] = 1\n",
    "            else:\n",
    "                dic[answers[i] + 1] += 1\n",
    "        res = 0\n",
    "        for key, value in dic.items():\n",
    "            if key >= value:\n",
    "                res += key \n",
    "            else:\n",
    "                res += math.ceil(value / key) * key\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        n = len(answers)\n",
    "        dp = [0]*1000\n",
    "        dp[0] = 0\n",
    "        existing = [0]*1000\n",
    "        for i in range(n):\n",
    "            if existing[answers[i]] == 0:\n",
    "                existing[answers[i]] = answers[i]\n",
    "                dp[i] = dp[i-1] + answers[i] + 1\n",
    "            else:\n",
    "                existing[answers[i]] -= 1\n",
    "                dp[i] = dp[i-1]\n",
    "        print(dp[:n])\n",
    "        return dp[n-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        cnts = collections.Counter(answers)\n",
    "        ans = 0\n",
    "        for k in cnts:\n",
    "            cnt = cnts[k]\n",
    "            ans += cnt // (k + 1) * (k + 1)\n",
    "            if cnt % (k + 1) > 0: ans += k + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, nums: List[int]) -> int:\n",
    "        dic={}\n",
    "        a=[]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in a:\n",
    "                a.append(nums[i])\n",
    "            if nums[i] not in dic:\n",
    "                dic[nums[i]]=1\n",
    "            else:\n",
    "                dic[nums[i]]+=1\n",
    "        s=0\n",
    "        for i in range(len(a)):\n",
    "            if a[i]==0:\n",
    "               s+=dic[a[i]]\n",
    "            else:\n",
    "                if dic[a[i]]>a[i]+1:\n",
    "                    if  dic[a[i]]%(a[i]+1)!=0:\n",
    "                        s+=(dic[a[i]]//(a[i]+1)+1)*(a[i]+1)\n",
    "                    else:\n",
    "                        s+=dic[a[i]]\n",
    "                else:\n",
    "                    s+= a[i]+1\n",
    "        return s\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        #同一颜色的兔子回答的数值必然是一样的\n",
    "# 但回答同样数值的，不一定就是同颜色兔子\n",
    "        #应该让「同一颜色的兔子数量」尽量多，从而实现「总的兔子数量」最少。\n",
    "        answers.sort()\n",
    "        i, ans, n = 0, 0, len(answers)\n",
    "        while i < n:\n",
    "            cur = answers[i]\n",
    "            ans += (cur + 1)\n",
    "            while cur > 0 and i + 1 < len(answers) and answers[i] == answers[i+1]:\n",
    "                #将后面的 cnt 个 cnt 进行忽略。\n",
    "                cur -= 1\n",
    "                i += 1\n",
    "            i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        numMap = defaultdict(lambda:[0, 0])\n",
    "        for eachAns in answers:\n",
    "            if numMap[eachAns + 1][1]:\n",
    "                numMap[eachAns + 1][1] -= 1\n",
    "            else:\n",
    "                numMap[eachAns + 1][0] += 1\n",
    "                numMap[eachAns + 1][1] = eachAns\n",
    "        return sum((num*numNum[0] for num, numNum in numMap.items()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        n = len(answers)\n",
    "       \n",
    "        ans = 0\n",
    "        nums = {}\n",
    "        for count in answers:\n",
    "            if count not in nums:\n",
    "                nums[count] = count\n",
    "                ans += count + 1\n",
    "            else:\n",
    "                if nums[count] != 0:\n",
    "                    nums[count] -= 1\n",
    "                else:\n",
    "                    nums[count] = count\n",
    "                    ans += count + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        n = len(answers)\n",
    "        dp = [0]*n\n",
    "        dp[0] = 0\n",
    "        existing = [0]*1000\n",
    "        for i in range(n):\n",
    "            if existing[answers[i]] == 0:\n",
    "                existing[answers[i]] = answers[i]\n",
    "                dp[i] = dp[i-1] + answers[i] + 1\n",
    "            else:\n",
    "                existing[answers[i]] -= 1\n",
    "                dp[i] = dp[i-1]\n",
    "        print(dp[:n])\n",
    "        return dp[n-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        # count = Counter(answers)\n",
    "        # result = 0\n",
    "        \n",
    "        # for k, v in count.items():\n",
    "        #     groups = (v + k) // (k + 1)\n",
    "        #     result += groups * (k + 1)\n",
    "        \n",
    "        # return result\n",
    "\n",
    "        count = {}\n",
    "    \n",
    "        for ans in answers:\n",
    "            count[ans] = count.get(ans, 0) + 1\n",
    "        \n",
    "        rabbits = 0\n",
    "        for ans, freq in count.items():\n",
    "            rabbits += (freq + ans) // (ans + 1) * (ans + 1)\n",
    "        \n",
    "        return rabbits\n",
    "        '''\n",
    "        The numRabbits function takes one parameter, answers, which is a list of integers representing the answers given by the rabbits.\n",
    "The algorithm uses a dictionary called count to store the frequency of different answers. The key in the dictionary is the answer, and the value is the frequency.\n",
    "The algorithm iterates through the answers list and updates the count dictionary.\n",
    "After counting the frequencies, the algorithm calculates the minimum number of rabbits. For each answer ans and its frequency freq, it adds (freq + ans) // (ans + 1) * (ans + 1) to the rabbits count.\n",
    "The term (freq + ans) // (ans + 1) calculates how many groups of rabbits with the same answer can be formed.\n",
    "Multiplying by (ans + 1) gives the total number of rabbits in those groups.\n",
    "The resulting rabbits count is the minimum number of rabbits in the forest\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        def lt781(answers):\n",
    "            answers.sort()\n",
    "            pairs=[]\n",
    "            st=0\n",
    "            for i in range(len(answers)):\n",
    "                if answers[i]!=answers[st]:\n",
    "                    pairs.append([answers[st]+1,i-st])\n",
    "                    st=i\n",
    "            pairs.append([answers[st]+1, len(answers) - st])\n",
    "            res=0\n",
    "            for a,b in pairs:\n",
    "                res+=math.ceil(b/a)*a\n",
    "            return res\n",
    "\n",
    "            # d=defaultdict(int)\n",
    "            # for num in answers:d[num]+=1\n",
    "            # pairs=[[k+1,v] for k,v in d.items()]\n",
    "            # res=0\n",
    "            # for a,b in pairs:\n",
    "            #     res+=math.ceil(b/a)*a\n",
    "            # return res\n",
    "        return lt781(answers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "\n",
    "        # nums = 0\n",
    "        # dict = {}\n",
    "\n",
    "        # for i in answers :\n",
    "        #     if i in dict :\n",
    "        #         dict[i] += 1\n",
    "        #         if dict[i] == i + 1 :\n",
    "        #             nums = nums + i + 1\n",
    "        #             del dict[i]\n",
    "        #     else :\n",
    "        #         dict[i] = 1\n",
    "        #         if dict[i] == i + 1 :\n",
    "        #             nums = nums + i + 1\n",
    "        #             del dict[i]\n",
    "        # for i in dict.keys() :\n",
    "        #     nums = nums + i + 1\n",
    "        \n",
    "        # return nums\n",
    "\n",
    "\n",
    "        ## 解法二\n",
    "        import collections\n",
    "        count = 0\n",
    "        hash = collections.defaultdict(int)\n",
    "        for i in answers:\n",
    "            hash[i] += 1\n",
    "            if hash[i] > i:\n",
    "                count += hash[i]\n",
    "                hash.pop(i)\n",
    "        \n",
    "        for i in hash.keys():\n",
    "            count += i + 1\n",
    "\n",
    "        return count\n",
    "                \n",
    "                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        ans=0\n",
    "        cnt=Counter(answers)\n",
    "        for i,v in cnt.items():\n",
    "            ans+=(i+v)//(i+1)*(i+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        import math\n",
    "        hash = {}\n",
    "        res = 0\n",
    "        for i in answers:\n",
    "            if i not in hash:\n",
    "                hash[i] = 1\n",
    "            else:\n",
    "                hash[i] += 1\n",
    "        for j in hash:\n",
    "            hash[j] = max(1, math.ceil(hash[j]/(j+1)))\n",
    "            res += hash[j]*(j+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        if len(answers)<2:\n",
    "            return (answers[0]+1)\n",
    "        num = 0\n",
    "        answers.sort()\n",
    "        print(answers)\n",
    "        cnt = answers[0]+1\n",
    "        for i in range(1,len(answers)):\n",
    "            if answers[i-1]==answers[i] and answers[i] != 0:\n",
    "                num += 1\n",
    "                if answers[i]>=num:\n",
    "                    continue\n",
    "                else: \n",
    "                    cnt += answers[i]+1\n",
    "                    num = 0\n",
    "            else:\n",
    "                num = 0\n",
    "                cnt += answers[i]+1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "\n",
    "        cnt = collections.Counter(answers)\n",
    "        res = sum((cnt[x]+x)//(x+1)*(x+1) for x in cnt)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        count=collections.Counter(answers)\n",
    "        ans=sum((x+y)//(y+1)*(y+1) for y,x in count.items())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        dic = {}\n",
    "        for i,s in enumerate(answers):\n",
    "            if s in dic:\n",
    "                dic[s]+=1\n",
    "            else:\n",
    "                dic[s]=1\n",
    "        res = 0\n",
    "        for i,num in dic.items():\n",
    "            if i ==0:\n",
    "                res +=num\n",
    "            elif i+1<num:\n",
    "                res +=ceil(num/(i+1))*(i+1)\n",
    "            else:\n",
    "                res += i+1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        dic={}\n",
    "        for num in answers:\n",
    "            if num not in dic:\n",
    "                dic[num]=1\n",
    "            else:\n",
    "                dic[num]+=1\n",
    "        result=0\n",
    "        for key,val in dic.items():\n",
    "            p=val//(key+1)\n",
    "            if val%(key+1)!=0:\n",
    "                p+=1\n",
    "            result+=p*(key+1)\n",
    "        return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def numRabbits(self, answers):\n",
    "        a = Counter(answers)\n",
    "        t1 = len(answers)\n",
    "        for i in a.keys():\n",
    "            t = a[i]%(i+1)\n",
    "            if t>0:\n",
    "                t1+=i+1-t\n",
    "        return t1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\r\n",
    "class Solution:\r\n",
    "    def numRabbits(self, answers: List[int]) -> int:\r\n",
    "        counter=Counter(answers)\r\n",
    "        ret=0\r\n",
    "        for k,v in counter.items():\r\n",
    "            ret+=((k+v)//(k+1))*(k+1)\r\n",
    "\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        #贪心思想\n",
    "        ans=0\n",
    "        cnt=Counter(answers)\n",
    "        for i,v in cnt.items():\n",
    "            ans+=ceil(v/(i+1))*(i+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        from collections import Counter\n",
    "        nums = Counter(answers)\n",
    "        ans = 0\n",
    "        for x, y in nums.items():\n",
    "            ans += (x + y) // (x + 1) * (x + 1)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        count = Counter(answers)\n",
    "        ans = sum((x + y) // (y + 1) * (y + 1) for y, x in count.items())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        count = {}\n",
    "        ans = 0\n",
    "        for rab in answers:\n",
    "            if rab not in count :\n",
    "                count[rab] = rab\n",
    "            elif count[rab] != 0:\n",
    "                count[rab] -= 1\n",
    "            else:\n",
    "                count[rab] = rab\n",
    "            ans += 1\n",
    "        \n",
    "        for val in count.values():\n",
    "            ans += val\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\" \n",
    "    2023-10-11\n",
    "        假设回答为 [2 2 2 2], 在该回答中, 前三个 2 可以归结为一种颜色, 最后一个 2 归结为另一个颜色\n",
    "        假设一组回答为 [y y y ... y] 共有 x 个, 对于第一个 y 来说, 表示属于第一种颜色的有 y+1 只(y 为其他兔子, +1 表示回答者), 一共有 x 只兔子, 则 x 只兔子可以划分的颜色种数位 ceil: x / (y+1)\n",
    " \"\"\"\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        count = Counter(answers)  ## y: x, 表示回答还有 y 只兔子的个数位 x\n",
    "        result = 0\n",
    "        for y, x in count.items():\n",
    "            result += math.ceil(x / (y + 1)) * (y + 1)  ## NOTE 官方的写法是向上取整的另一种形式\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        counts = {}\n",
    "        result = 0\n",
    "        for ans in answers:\n",
    "            if ans in counts:\n",
    "                num_cur, num_max = counts[ans]\n",
    "                if num_cur >= num_max:\n",
    "                    result += num_max\n",
    "                    counts[ans] = (1, ans + 1)\n",
    "                else:\n",
    "                    counts[ans] = (num_cur + 1, num_max)\n",
    "            else:\n",
    "                counts[ans] = (1, ans + 1)\n",
    "            # print(result, counts)\n",
    "        result += sum(value[1] for value in counts.values())\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        if len(answers)<2:\n",
    "            return (answers[0]+1)\n",
    "        num = 0\n",
    "        answers.sort()\n",
    "        print(answers)\n",
    "        cnt = answers[0]+1\n",
    "        for i in range(1,len(answers)):\n",
    "            if answers[i-1]==answers[i] and answers[i] != 0:\n",
    "                num += 1\n",
    "                if answers[i]>=num:\n",
    "                    continue\n",
    "                else: \n",
    "                    cnt += answers[i]+1\n",
    "                    num = 0\n",
    "            else:\n",
    "                num = 0\n",
    "                cnt += answers[i]+1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        from collections import Counter\n",
    "        cnt=Counter(answers)\n",
    "        ans=0\n",
    "        for key,value in cnt.items():\n",
    "            ans=ans+(value//(key+1))*(key+1)\n",
    "            if value%(key+1)!=0:\n",
    "                ans+=key+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        answers.sort()\n",
    "        num = answers[0]+1\n",
    "        now = answers[0]\n",
    "        count = answers[0]\n",
    "        for i in range(1,len(answers)):\n",
    "            if answers[i]!=now:\n",
    "                    now = answers[i]\n",
    "                    num += answers[i]+1\n",
    "                    count = answers[i]\n",
    "            else:\n",
    "                if count ==0:\n",
    "                    num += answers[i]+1\n",
    "                    count = answers[i]\n",
    "                else:\n",
    "                    count -=1\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "\n",
    "        # answers.sort()\n",
    "        # num = []\n",
    "        # num_count = []\n",
    "        # count = 0\n",
    "        # n = 0\n",
    "        # for i in range(0,len(answers)):\n",
    "        #     if i == 0:\n",
    "        #         num.append(answers[i])\n",
    "        #         count = count+1\n",
    "        #     else:\n",
    "        #         if answers[i] == answers[i-1]:\n",
    "        #             count = count + 1\n",
    "        #         else:\n",
    "        #             num_count.append(count)\n",
    "        #             count = 1\n",
    "        #             num.append(answers[i])\n",
    "        # num_count.append(count)\n",
    "        \n",
    "        # for i in range(0,len(num)):\n",
    "        # # if num[i] != 0:\n",
    "        #     if num_count[i] <= num[i]+1:\n",
    "        #         n = num[i] + 1 + n\n",
    "        #     else:\n",
    "        #         if num_count[i] % (num[i]+1) == 0:\n",
    "        #             x = num_count[i] // (num[i]+1)\n",
    "        #             n = x * (num[i]+1) + n\n",
    "        #         else:\n",
    "        #             x = num_count[i] // (num[i]+1)\n",
    "        #             n = (x+1) * (num[i]+1) + n\n",
    "        # # else:\n",
    "        # #     n = n + num_count[i]\n",
    "        # return n\n",
    "\n",
    "        num_count = dict()\n",
    "        for i in range(len(answers)):\n",
    "            if answers[i] not in num_count:\n",
    "                num_count[answers[i]] = 1\n",
    "            else:\n",
    "                num_count[answers[i]] += 1\n",
    "        \n",
    "        res = 0\n",
    "        for c in num_count:\n",
    "            if num_count[c] % (1 + c) == 0:\n",
    "                res = res + num_count[c]\n",
    "            else:\n",
    "                res = res + int(num_count[c] / (1 + c)) * (1 + c) + (1 + c)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        freq,ans=Counter(answers),0\n",
    "        for k,v in freq.items():\n",
    "            ans+=(ceil(v/(k+1))*(k+1))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        count=Counter(answers)\n",
    "        ans=sum((x+y)//(y+1)*(y+1) for y,x in count.items())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: list[int]) -> int:\n",
    "        count = collections.Counter(answers)\n",
    "        ans = sum((x + y) // (y + 1) * (y + 1) for y, x in count.items())\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        c_answers=Counter(answers)\n",
    "        return sum([(x+y)//(y+1)*(y+1) for y,x in c_answers.items()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def numRabbits(self, answers):\n",
    "        li = set(answers)\n",
    "        di = {}\n",
    "        k = di.keys()\n",
    "        su = 0\n",
    "        for i in answers:\n",
    "            if i not in k:\n",
    "                di[i]=1\n",
    "            else:\n",
    "                di[i]+=1\n",
    "        for i in li:\n",
    "            if i==0:\n",
    "                su=su + di[0]\n",
    "            else:\n",
    "                a= i+1\n",
    "                b= di[i]\n",
    "                if b%a==0:\n",
    "                    num = b // a \n",
    "                else:\n",
    "                    num=b//a+1\n",
    "                su = su + a*num\n",
    "        return su"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        cnt = collections.Counter(answers)\n",
    "\n",
    "        return sum((cnt[x] + x)//(x+1)*(x+1) for x in cnt)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        dic = {}\n",
    "        res = 0\n",
    "        for num in answers:\n",
    "            if str(num) not in dic or dic[str(num)] > num:\n",
    "                dic[str(num)] = 1\n",
    "                res += num + 1\n",
    "            else:\n",
    "                dic[str(num)] += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        ans = dict(Counter(answers))\n",
    "        print(ans)\n",
    "        s = 0\n",
    "        for k, v in ans.items():\n",
    "            s = s + (k + 1) * ((v-1) // (k + 1)+1)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        answers.sort()\n",
    "        i ,ans ,n = 0 ,0 ,len(answers)\n",
    "        while i < n :\n",
    "            cur = answers[i]\n",
    "            ans += (cur + 1)\n",
    "            while cur > 0 and i + 1 < len(answers) and answers[i] == answers[i+1]:\n",
    "                cur -= 1\n",
    "                i += 1\n",
    "            i += 1\n",
    "        return ans        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numRabbits(self, answers: List[int]) -> int:\r\n",
    "        ans = 0\r\n",
    "        counter = Counter(answers)\r\n",
    "        for element, count in counter.items():\r\n",
    "            if count % (element + 1) == 0:\r\n",
    "                ans += count\r\n",
    "            else:\r\n",
    "                ans += count - count % (element + 1) + element + 1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        \n",
    "        diction = {}\n",
    "        nu = 0\n",
    "        for i in answers:\n",
    "            if i in diction:\n",
    "                if diction[i] == 0:\n",
    "                    diction[i] = i\n",
    "                    nu += i + 1\n",
    "                else:\n",
    "                    diction[i] -= 1\n",
    "            else:\n",
    "                diction[i] = i\n",
    "                nu += i + 1\n",
    "\n",
    "        return nu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRabbits(self, answers: List[int]) -> int:\n",
    "        dic = defaultdict(int)\n",
    "        for x in answers:\n",
    "            dic[x] += 1\n",
    "        res = 0\n",
    "        print(dic)\n",
    "        for k, v in dic.items():\n",
    "            if k == 0:\n",
    "                res += v\n",
    "            elif k + 1 >= v: # 都在这了\n",
    "                res += (k+1)\n",
    "            else: # 有好多不同的颜色\n",
    "                res += (k+1) * math.ceil(v/(k+1))\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
